package com.leetcode.partition18;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author `RKC`
 * @date 2022/1/29 9:55
 */
public class LC1765地图中的最高点 {

    private static final int N = 1010, M = 1010;
    private static final int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static int n = 0, m = 0;
    private static Queue<int[]> q = new ArrayDeque<>(N * M);
    private static boolean[][] st1 = new boolean[N][M], st2 = new boolean[N][M];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        int[][] isWater = new int[n][m];
        for (int i = 0; i < n; i++) {
            s = reader.readLine().split(" ");
            for (int j = 0; j < m; j++) isWater[i][j] = Integer.parseInt(s[j]);
        }
        int[][] ans = highestPeak(isWater);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) writer.write(ans[i][j] + " ");
            writer.write("\n");
        }
        writer.flush();
    }

    public static int[][] highestPeak(int[][] isWater) {
        n = isWater.length;
        m = isWater[0].length;
        int[][] ans = new int[n][m];
        //找出所有的水地，并将附近的陆地加入队列
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (isWater[i][j] == 1) {
                    q.add(new int[]{i, j});
                }
            }
        }
        while (!q.isEmpty()) {
            int[] pair = q.poll();
            int x = pair[0], y = pair[1], h = ans[x][y];
            st1[x][y] = true;
            for (int[] dir : dirs) {
                int nx = dir[0] + x, ny = dir[1] + y;
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || st1[nx][ny]) continue;
                st1[nx][ny] = true;
                if (isWater[nx][ny] == 0 && !st2[nx][ny]) {
                    ans[nx][ny] = h + 1;
                    st2[nx][ny] = true;
                }
                q.add(new int[]{nx, ny});
            }
        }
        return ans;
    }
}
